package class03;

import java.util.Arrays;

// 给定一个正数数组arr，代表若干人的体重
// 再给定一个正数limit，表示所有船共同拥有的载重量
// 每艘船最多坐两人，且不能超过载重
// 想让所有的人同时过河，并且用最好的分配方法让船尽量少
// 返回最少的船数
// 测试链接 : https://leetcode.com/problems/boats-to-save-people/
public class Code05_BoatsToSavePeople {

	public static int numRescueBoats1(int[] arr, int limit) {
		// 如果数组为空或长度为0，不需要船
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 获取数组长度
		int N = arr.length;
		// 对数组进行排序，便于后续处理
		Arrays.sort(arr);
		// 如果最重的人超过了船的载重限制，无法完成运输
		if (arr[N - 1] > limit) {
			return -1;
		}
		// 查找体重小于等于limit/2的最右位置
		int lessR = -1;
		// 从右向左遍历数组
		for (int i = N - 1; i >= 0; i--) {
			// 如果当前人体重小于等于limit的一半
			if (arr[i] <= (limit / 2)) {
				lessR = i;
				break;
			}
		}
		// 如果没有人体重小于等于limit的一半，每人需要一条船
		if (lessR == -1) {
			return N;
		}
		// 初始化双指针
		int L = lessR;
		int R = lessR + 1;
		// 记录无法配对的人数
		int noUsed = 0;
		// 从右向左处理体重较轻的人
		while (L >= 0) {
			// 记录当前L位置的人能与多少个较重的人配对
			int solved = 0;
			// 尝试将L位置的人与较重的人配对
			while (R < N && arr[L] + arr[R] <= limit) {
				R++;
				solved++;
			}
			// 如果无法配对
			if (solved == 0) {
				noUsed++;
				L--;
			} else {
				// 如果可以配对，更新L的位置
				L = Math.max(-1, L - solved);
			}
		}
		// 计算体重较轻的人数
		int all = lessR + 1;
		// 计算已配对的较轻人数
		int used = all - noUsed;
		// 计算未配对的较重人数
		int moreUnsolved = (N - all) - used;
		// 返回所需船数：已配对人数 + 未配对的较轻人数所需船数 + 未配对的较重人数
		return used + ((noUsed + 1) >> 1) + moreUnsolved;
	}

	// 首尾双指针的解法
	public static int numRescueBoats2(int[] people, int limit) {
		// 对人员体重进行排序
		Arrays.sort(people);
		// 记录所需船数
		int ans = 0;
		// 左指针指向最轻的人
		int l = 0;
		// 右指针指向最重的人
		int r = people.length - 1;
		// 当前船上的总重量
		int sum = 0;
		// 当左指针不超过右指针时继续循环
		while (l <= r) {
			// 如果只剩一个人，计算这一个人的体重；否则计算最轻和最重两个人的体重和
			sum = l == r ? people[l] : people[l] + people[r];
			// 如果两人总重量超过限制
			if (sum > limit) {
				// 只能运送重的人，右指针左移
				r--;
			} else {
				// 两人可以同船，左指针右移，右指针左移
				l++;
				r--;
			}
			// 船的数量加1
			ans++;
		}
		// 返回所需最少船数
		return ans;
	}

}